1. Field of the Invention
The present invention relates to the field of computer graphics images of 3D (three-dimensional) scenes or spaces. The present invention also relates to a method and a computer system for rendering computer graphics images using ray-tracing.
2. Background of the Invention
Ray-Tracing (RT) is a fundamental, much investigated and much used computer graphics algorithm for solving primitive/ray intersections, for example in displaying three dimensional objects and scenes on two-dimensional displays or screens. Primitives are used to describe the scene, while rays are used to model light paths. Unlike rasterization, RT can accommodate any ray parameterization, which makes it useful for numerous rendering problems. The basic algorithm for solving a RT problem, often referred to as naïve ray-tracing, is well-known and comprises intersecting each ray used for the rendering of a graphical image with all primitives defining a particular 3D (three-dimensional) scene. However, the trivial complexity of this algorithm—O(primitives×rays)—is not suitable for most applications that nowadays handle large quantities of rays and primitives. As such, naïve RT as proposed by Whitted (1980) has been quickly discarded and spatial subdivision data structures have been subsequently used and widely investigated to reduce the per-ray complexity of the algorithm. See, Whitted, T., “An improved illumination model for shaded display,” Communication of the ACM, Vol. 23, No. 6, 343-349 (1980). Indeed, naïve ray-tracing can be millions of time slower than current approaches when very large scenes with millions of primitives are handled.
All algorithms proposed subsequent to Whitted carry out the following steps: 1: Compute a spatial subdivision data structure; 2: Trace rays (and possibly continue constructing spatial subdivision); to solve intersections between rays and primitives like triangle. Such algorithms require extra memory on the system to solve the problem.
Early proposed spatial subdivisions included kd-trees (Bentley, J. L., “Multidimensional binary search trees used for associative searching,” Communications of the ACM, Vol. 18, No. 9, 509-517 (1975)), Bounding Volume Hierarchies (BVH) (S. Rubin and J. Whitted, “A 3-dimensional representation for fast rendering of complex scenes,” Proceedings of SIGGRAPH'80, Vol. 14, No. 3, 110-116; Kay, T. and Kajiya, J. “Ray Tracing Complex Scenes,” Proceedings of SIGGRAPH'86, Vol. 20, No. 4, 269-278 (1986)), BSP-trees (Fuchs, H., Kedem, Z. M., and Naylor B. F., “On visible surface generation by a priori tree structures,” Proceedings of SIGGRAPH 1980, Vol. 23, 124-133 (1980)), Octrees (Glassner A., “Space subdivision for fast ray tracing,” IEEE Computer Graphics and Applications, Vol. 4, No. 10, 15-22 (1984)) and grids (Fujimoto, A., Tanaka, T. and Iwata, K. “Arts: Accelerated ray-tracing system,” IEEE Computer Graphics and Applications, Vol. 6, No. 4, 16-26 (1986)). All of these implementations use spatial subdivision data structures that require additional memory to solve the problem.
For rendering static scenes, RT has usually been considered a very efficient rendering technique if the construction times of the acceleration data structure are ignored. However, recent efforts have focused more on the rendering of scenes containing dynamic objects/primitives, and therefore the construction times must now be considered as the spatial subdivision data structure needs to be modified/recomputed each time the scene is modified. This raises a few issues as extra construction time is likely to provide a better tracing rate, while faster construction times may see tracing times degrading. As such, Wald et al. (2006) recognized that a good balance could be difficult to find, and proposed the use of grids as an original alternative to the long construction times of hierarchical space subdivision data structures, such as kd-trees. See, Wald, I., Ize, T., Kensler, A., Knoll, A., and Parker, S. G., “Ray Tracing Animated Scenes using Coherent Grid Traversa,” Proceedings of ACM SIGGRAPH 2006, Boston, Vol. 25, No. 3, 485-493 (2006) and Wald, I., Boulos, S., and Shirley, P., “Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies Ingo,” ACM Transaction On Graphics, Vol. 26, No 1, Article 6 (2006).
As grids are renowned for a lower tracing complexity of O(n^⅓) (Cleary, J. G. and Wyvill, G., “Analysis of an algorithm for fast ray tracing using uniform space subdivision,” The Visual Computer, Vol. 4, No. 2, 65-83 (1988); Ize, T., Shirley, P. and Parker, S. G., “Grid Creation Strategies for Efficient Ray Tracing,” Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, 27-32 (2007)), a fast packet traversal was also proposed. Further work on grids has then been produced by Lagae, A. and Dutré, P., “Compact, Fast and Robust Grids for Ray Tracing,” Proceedings of the Eurographics symposium on Rendering, 1235-1244 (2008), focusing more on both the grid construction times and low memory usage. Results produced by Lagae and Dutré clearly show that grid structure can be computed at an extreme speed and that rendering times are more ray-bounded. However, some discrepancy in rendering times given by Lagae and Dutré is visible, and grids seem to perform noticeably worse for scenes with anisotropic triangles, as predicted by Ize et al.
The use of tree structures is also described in the content of US 2008/0043018 which is incorporated by reference herewith.
Kd-trees data structures are slower to construct than grids, although more reliable for tracing. However, Hunt et al., “Fast kd-tree Construction with an Adaptive Error-Bounded Heuristic,” Proceedings of the 2006 IEEE Symposium on Raytracing, 81-88 (2006) and Shevtsov, M., Soupikov, A. and Kapustin, A., “Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes,” Proceedings of Eurographics 2007, 395-404 (2007) have introduced a method that achieves an interactive construction of the data structure that even includes a very fast Surface Area Heuristic (SAH) estimation. The tracing part of Shevtsov et al.'s algorithm was managed by a very fast MLRT algorithm, with the observation that a reduction in the tree quality could be suitable if fewer rays are to be traced. Zhou et al. have overcome the task of porting the kd-tree construction on a GPU, showing some clear acceleration. See, Zhou, K., Hou, Q., Wang, R. and Guo., B. “Real-Time KD-Tree Construction on Graphics Hardware,” Proceedings of In proceedings of ACM SIGGRAPH ASIA 2008 (2008). In comparison with the grids, the use of the kd-trees seems much more primitive-bounded, as a lot more rendering time is generally spent constructing the spatial subdivision data structure and much less in tracing.
For animated scenes such as movies, a reconstruction of a full data structure at each frame may be losing some information, and a simple update of the data structure is sometimes more logical. Wald et al. (2006) and Lauterbach, C., Yoon, S. and Manocha, D., “RTDEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs,” Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, 39-45 (2006) thus independently demonstrated that Bounding Volume Hierarchies (BVH) data structures are well suited to this task, although the time needed to compute the original BVH is not interactive for moderately large scenes.
US 2009/0128562, which is incorporated by reference herewith, describes a ray tracing method, wherein a geometry acceleration data structure is determined and stored for a given scene prior to performing the actual ray-tracing. Ray/primitive intersections are tested using a parallel testing resource.
A drawback to all previously mentioned approaches is that the memory footprint, i.e. the memory resources required, may vary between the frames, which is a disadvantage with regard to software engineering, as dynamic allocation should then be involved to optimize memory management on the system such that memory is only allocated when needed. Instead, many approaches do not include the cost of dynamic allocation in their discussion and just make use of pre-allocated memory. Nonetheless, Lagae and Dutré presented a framework for dynamic re-allocation with limited impact. The importance of memory management was acknowledged by Wachter and Keller, who proposed Bounding Interval Hierarchies (BIHs) where the maximum memory usage is linearly bounded by the number of triangles. See, Wachter, C. and Keller, A., “Instant Ray Tracing: The Bounding Interval Hierarchy,” Proceedings of Eurographics Symposium on Rendering 2007, 139-149 (2006) and Wachter, C. and Keller, A., “Terminating Spatial Hierarchies by A Priori Bounding Memory,” Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, 41-46 (2007).
Although the memory usage is not exactly deterministic, this BIH property is possible because there is no need to replicate triangle indices. An original, on demand construction was also demonstrated, where only a partial tree is constructed before tracing. During the backtracking tracing process, the construction is eventually completed for temporary leaf nodes that are reached, possibly avoiding processing occluded regions of the scene. As a result, the memory needed for the BIH is typically only a fraction of that needed for other methods.
As mentioned above, all methods suggested so far make use of a compulsory additional data structure, such as the spatial subdivision data structure, which in RT is often seen as a burden by developers, and makes RT more complex. Therefore, a new method based on the naïve algorithm that can directly solve intersections between a set of rays and a set of primitives at no or reduced additional memory cost is of much interest, especially if the method is proven to be fast.